package summer.greedy;

import java.util.Arrays;

public class Solution376 {
    public static void main(String[] args) {
        int[] nums = {1,7,4,9,2,5};
        System.out.print(wiggleMaxLength(nums));;
    }

    public int wiggleMaxLength1(int[] nums) {
        int res = 1;
        int pre = 0;
        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i] - nums[i - 1];
            if (cur > 0 && pre <= 0 || cur < 0 && pre >= 0) {
                res++;
                pre = cur;
            }
        }
        return res;
    }

    public static int wiggleMaxLength(int[] nums) {
        int[][] dp = new int[nums.length][2];
        int[][] dp1 = new int[nums.length][2];
        Arrays.fill(dp, new int[]{1, 1});
//        dp[0][0] = 1;
//        dp[0][1] = 1;
        for (int i = 0; i < nums.length; i++) {
            Arrays.fill(dp1[i], 1);
        }
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i][0] = Math.max(dp[j][1] + 1, dp[i][0]);
                } else if (nums[i] < nums[j]) {
                    dp[i][1] = Math.max(dp[j][0] + 1, dp[i][1]);
                }
            }
            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
        }
        return res;
    }
}
